﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Era
{
    class Eratosthenes
    {
        /// <summary>
        /// 老老实实挨个筛
        /// </summary>
        /// <returns></returns>
        public List<int> GetPrime1(int n)
        {
            List<bool> isPrime = new List<bool>(n + 1);
            for (int i = 0; i <= n; i++)
                isPrime.Add(true);
            List<int> prime = new List<int>();
            prime.Add(2);
            for (int i = 3; i <= (int)Math.Sqrt(n); i += 2)
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            for (int i = 2; i <= n; i++)
                if (i % 2 != 0 && isPrime[i])
                    prime.Add(i);
            return prime;
        }

        /// <summary>
        /// 从第一个素数2开始，筛掉其N以内倍数；跳到下一个没被筛的数，循环。
        /// </summary>
        /// <returns></returns>
        public List<int> GetPrime2(int n)
        {
            List<bool> isPrime = new List<bool>(n + 1);
            for (int i = 0; i <= n; i++)
                isPrime.Add(true);
            List<int> prime = new List<int>();
            for (int i = 2; i < n; i++)
                if (isPrime[i])
                { 
                    prime.Add(i);
                    for (int j = i * i; j <= n; j += i)
                        isPrime[j] = false;
                }
            return prime;
        }

        /// <summary>
        /// 循环相除素数直到除无可除
        /// </summary>
        /// <returns></returns>
        public List<int> GetAllPrime1(int n)
        {
            List<int> primes = GetPrime2((int)Math.Sqrt(n));
            List<int> prime = new List<int>();
            bool flag = true;
            while (flag)
            {
                int i = 0;
                //检测素数表是否有其因数
                for (; i < primes.Count; i++)
                    if (n % primes[i] == 0)
                    {
                        prime.Add(primes[i]);
                        n /= primes[i];
                        break;
                    }
                if(i== primes.Count)
                {
                    prime.Add(n);
                    break;
                }
            }
            return prime;
        } 

    }
}
